package lib

import "sort"

func init() {
	Probs = append(Probs, Problem{
		Num:         1885,
		Discription: "统计nums1[i] + nums1[j] > nums2[i] + nums2[j] 的对数",
		Level:       2,
		Labels: map[string]int{
			"排序":    1,
			"差分数组":  1,
			"双指针滑动": 1,
		},
	})
}

//差分数组也可以是不同数组的差分
//转化为(nums1[i]-nums2[i])+(nums1[j]-nums2[j])>0的对数
func CountPairs(nums1 []int, nums2 []int) int64 {
	n := len(nums1)
	diff := make([]int, n)
	for i := 0; i < n; i++ {
		diff[i] = nums1[i] - nums2[i]
	}

	//排序差分数组
	sort.Ints(diff)
	left := 0
	right := n - 1
	res := int64(0)
	//每次固定right，移动left
	//因为right往右移动后，left左边是不可能有值来满足right的
	for left < right {
		for left < right && diff[left]+diff[right] <= 0 {
			left++
		}

		res += int64(right - left)
		right--
	}

	return res
}
